#pragma once
#include <cassert>
#include <memory>

#include <library/table/table.h>
#include <library/tree/binary_tree.h>

template<class TKey, class TValue>
TBinaryTree<TKey, TValue> BuildOptimalBinaryTree(size_t elemCount, const TKey* keys, const TValue* values, const double* keyProbabilities, const double* missProbabilities);

namespace NOptimalBinaryTreeHelper {

template<class TKey, class TValue>
typename TBinaryTree<TKey, TValue>::TNode::TPtr BuildTree(const TTable<int>& root, const TKey* keys, const TValue* values, size_t from, size_t to) {
    typedef TBinaryTree<TKey, TValue> TTree;
    typedef typename TTree::TNode TNode;
    typedef typename TNode::TPtr TPtr;

    const size_t index = root(from, to);
    assert(index != -1);
    TPtr tree(new TNode(keys[index], values[index]));

    if (index != from) {
        tree->LeftChild = BuildTree(root, keys, values, from, index);
        tree->LeftChild->Parent = tree.get();
    }
    if (index + 1 != to) {
        tree->RightChild = BuildTree(root, keys, values, index + 1, to);
        tree->RightChild->Parent = tree.get();
    }
    return std::move(tree);
}

template<class TKey, class TValue>
TBinaryTree<TKey, TValue> BuildTree(const TTable<int>& root, const TKey* keys, const TValue* values) {
    return TBinaryTree<TKey, TValue>(BuildTree(root, keys, values, 0, root.RowsCount()));
}

void FillOptimalBinaryTreeTables(size_t elemCount, const double* keyProbabilities, const double* missProbabilities, TTable<double>& e, TTable<double>& w, TTable<int>& root, std::ostream* dbgOutput);

} // namespace NOptimalBinaryTreeHelper

template<class TKey, class TValue>
TBinaryTree<TKey, TValue> BuildOptimalBinaryTree(size_t elemCount, const TKey* keys, const TValue* values, const double* keyProbabilities, const double* missProbabilities, std::ostream* dbgOutput = nullptr) {
    TTable<double> e(elemCount + 1, elemCount + 1, -1); // мат ожидания. e(i, j) - мат ожидание 
    TTable<double> w(elemCount + 1, elemCount + 1, -1); // веса оптимальных поддеревьев (вероятность, что значение при поиске в дереве попадёт в данное поддерево) // Сумма от i до j keyProbabilities и от i до j + 1 missProbabilities
    TTable<int> root(elemCount, elemCount + 1, -1);

    NOptimalBinaryTreeHelper::FillOptimalBinaryTreeTables(elemCount, keyProbabilities, missProbabilities, e, w, root, dbgOutput);

    return std::move(NOptimalBinaryTreeHelper::BuildTree(root, keys, values));
}
